JavaScript数据结构与算法(搜索算法)

共计 1027 个字符，预计需要花费 3 分钟才能阅读完成。

顺序搜索

最基本的搜索算法，最低效的一种搜索算法。它的机制是，将每一个数据结构中的元素和要找的元素做比较。

function search(array, value) {for (let i = 0; i < array.length; i++) {if (value === array[i]) {return i}
  }
  return -1
}

console.log(search([1, 3, 5, 2, 0], 5))

二分搜索

这个算法要求被搜索的数据结构已排序。

function binarySearch(find, arr, start, end) {
  start = start || 0
  end = end || arr.length - 1

  if (start <= end && find >= arr[start] && find <= arr[end]) {if (arr[start] === find) {return start}
    if (arr[end] === find) {return end}

    let mid = Math.ceil((end + start) / 2)
    if (arr[mid] === find) {return mid} else if (arr[mid] > find) {return binarySearch(find, arr, start, mid - 1)
    } else {return binarySearch(find, arr, mid + 1, end)
    }
  }

  return -1
}

function quickSort(arr) {const { length} = arr
  if (length < 2) {return arr}

  let base = arr[0]
  let minArr = arr.slice(1).filter((item) => item <= base)
  let maxArr = arr.slice(1).filter((item) => item > base)

  return quickSort(minArr).concat(base).concat(quickSort(maxArr))
}

arr = quickSort([1, 3, 5, 2, 0])

console.log(...arr)
console.log(binarySearch(2, arr))

内插搜索

是改良版的二分搜索，只需改动 mid：

let mid = (start + Math.floor(((find - arr[start]) / (arr[end] - arr[start])) * (end - start)))

斐波那契查找

也是二分查找的一种提升算法，斐波那契查找也属于一种有序查找算法。